public class Samsung2 {
	// Fuck the java array
	// Original array
	/*
	 * 	19 57 74 73 94
		26 27 32 98 61
		40 88 49 38 25
		21 66 53 95 46
		80 23 58 39 89
	 * 
	 */
	private static final int[][] DATA = {
			{ 19, 26, 40, 21, 80 },
			{ 57, 27, 88, 66, 23 },
			{ 74, 32, 49, 53, 58 },
			{ 73, 98, 38, 95, 39 },
			{ 94, 61, 25, 46, 89 },
	};

	public static void main(String[] args) {
		// find the min
		int min = minValue(DATA[0]);
		int length = DATA.length;
		for (int i = 1; i < length; i++) {
			int temp_min = minValue(DATA[i]);
			if (temp_min < min)
				min = temp_min;
		}
		// Create the path tracker
		int[][] pathTracker = new int[length][length];
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				pathTracker[i][j] = -1;
			}
		}
		// Generate the path
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				// Get value of a cell
				// Check if it is the target
				if(DATA[i][j] == min) {
					pathTracker[i][j] = 0;
				} else {
					// While we can not find the min
					// Keep moving
					int[] trackingValue = nextValidMove(DATA, i, j);
					while(trackingValue[0] != min) {
						Common.printArray(trackingValue, "\t");
						trackingValue = nextValidMove(DATA, trackingValue[1], trackingValue[2]);
					}
				}
			}
		}
		
		for (int i = 0; i < length; i++) {
			Common.printArray(pathTracker[i], "\t");
			System.out.println();
		}
	}

	private static int minValue(final int[] data) {
		int min = data[0];
		for (int i = 0; i < data.length; i++) {
			min = min > data[i] ? data[i] : min;
		}
		return min;
	}

	/**
	* Find the next valid move
	* Move to the smallest value
	*/
	private static int[] nextValidMove(final int[][] data, final int current_x,
			final int current_y) {
		int[] result = { -1, current_x, current_y };
		// TrinhNX: laziness and bad performance :lol:
		int value = 0;
		// First item, assign the left
		try {
			value = data[current_x - 1][current_y];
			result[0] = value;
			result[1] = current_x - 1;
			result[2] = current_y;

		} catch (IndexOutOfBoundsException e) {
			// Not valid ? well, ignore
			System.out.println("Loi cmnr :v ");
		}
		// Second item, assign the right
		try {
			value = data[current_x + 1][current_y];
			if (result[0] == -1 || result[0] > value) {
				result[0] = value;
				result[1] = current_x + 1;
				result[2] = current_y;
			} else {
				System.out.println("Deo quan tam :v " + value);
			}
		} catch (IndexOutOfBoundsException e) {
			// Not valid ? well, ignore
			System.out.println("Loi cmnr :v ");
		}
		// Third item, assign the top	
		try {
			value = data[current_x][current_y - 1];
			if (result[0] == -1 || result[0] > value) {
				result[0] = value;
				result[1] = current_x;
				result[2] = current_y - 1;
			} else {
				System.out.println("Deo quan tam :v " + value);
			}
		} catch (IndexOutOfBoundsException e) {
			// Not valid ? well, ignore
			System.out.println("Loi cmnr :v ");
		}
		// Forth item, assign the bottom
		try {
			value = data[current_x][current_y + 1];
			if (result[0] == -1 || result[0] > value) {
				result[0] = value;
				result[1] = current_x;
				result[2] = current_y + 1;
			} else {
				System.out.println("Deo quan tam :v " + value);
			}
		} catch (IndexOutOfBoundsException e) {
			// Not valid ? well, ignore
			System.out.println("Loi cmnr :v ");
		}
		// Now we had the value / x / y
		Common.printArray(result, "\t");
		return result;
	}
}
